import pytest
from functools import wraps
import abc
class Comparable():
    __metaclass__ = abc.ABCMeta

    @abc.abstractclassmethod
    def compare(self,obj):
        pass

def check_sort(data):
    for i in range(0,len(data)-1):
        if data[i].compare(data[i+1]) >0:
            return False
    return True


class Selection():

    def sort(self,data):
        a=len(data)
        for i in range(0,a):
            minIdx=i
            for j in range(i+1,a):
                if self.less(data[j],data[minIdx]):
                    minIdx=j
            self.exch(data,i,minIdx)

    def show_exec(self,data,oldIdx,newIdx):
        print_string=""
        print_string2=""
        for i in range(len(data)):
            print_string += "{:2s} ".format(data[i])
            if i == oldIdx or i == newIdx :
               print_string2 += "{:2d} ".format(i)
            else :
               print_string2 += " "*(2+1)

        print(f"{print_string}\n{print_string2}")

    def exch(self,data,oldIdx,newIdx):
        temp=data[oldIdx]
        data[oldIdx]=data[newIdx]
        data[newIdx]=temp

    def less(self,target,source):
        diff=target.compare(source)
        return diff <0

class Insertion(Selection):

    def sort(self,data,step_factor=1,lo=None,hi=None):
        if lo is None:
            lo=0
        if hi is None:
            hi=len(data)-1
        #  print(f"step_factor:{step_factor}")
        for i in range(1*step_factor,hi+1,step_factor):
            for j in range(i,lo,-step_factor):
                preIdx=j-step_factor
                #  print(f"sort {preIdx} {j}")
                if(data[j].compare(data[preIdx])<0):
                    self.exch(data,j,preIdx)

class Shell(Insertion):

    def sort(self,data):
        count=len(data)
        h=1
        while (h < count/3):
            h=h*3+1
        while h >= 1:
            Insertion.sort(self,data,step_factor=h)
            h=h//3

class Merge(Insertion):

    def merge(self,data,lo,mid,hi):
        #  print(f"merge:{lo} {mid} {hi}")
        i=lo
        j=mid+1
        temp_data=data[:]
        for k in range(lo,hi+1):
            if i > mid :
                data[k]=temp_data[j]
                j+=1
            elif j > hi :
                data[k]=temp_data[i]
                i+=1
            elif temp_data[j].compare(temp_data[i]) < 0 :
                data[k]=temp_data[j]
                j+=1
            else :
                data[k]=temp_data[i]
                i+=1

    def sort(self,data,lo=0,hi=None):
        if hi is None:
            hi=len(data)-1
        if hi-lo < 5:
            Insertion.sort(self,data,lo=lo,hi=hi)
            return
        if hi <= lo :
            return
        mid = lo +(hi-lo)//2
        #  print(f"{lo} {mid} {hi}")
        self.sort(data,lo=lo,hi=mid)
        self.sort(data,lo=mid+1,hi=hi)
        self.merge(data,lo,mid,hi)

class Quick(Insertion):

    def sort(self,data,lo=None,hi=None):
        if lo is None:
            lo=0
        if hi is None:
            hi=len(data)-1
        if hi<=lo+5:
            Insertion.sort(self,data,lo=lo,hi=hi)
            return
        j=self.partion(data,lo,hi)
        self.sort(data,lo,j-1)
        self.sort(data,j+1,hi)

    def partion(self,data,lo,hi):
        i,j=lo,hi
        base=data[lo]
        while True :
            i+=1
            while not data[i].compare(base) >= 0 :
                i+=1
                if i>=hi:
                    break
            while not data[j].compare(base) <=0 :
                j-=1
                if j==lo:
                    break
            #  print(f"{i} {j}")
            if j <= i :
                break
            self.exch(data,i,j)
        self.exch(data,lo,j)
        #  print(f"{lo}----{hi}---{j}")
        return j




class Int(Comparable):

    def __init__(self,number):
        self.number=number

    def compare(self,obj):
        return self.number - obj.number

    def __str__(self):
        return str(self.number)

    def __repr__(self):
        return str(self.number)
    def __format__(self,format_spec):
        return "{:2d}".format(self.number)

def wrap_test(func):
    @wraps(func)
    def test(*args, **kwargs):
        import random
        data=[Int(random.randrange(0,100)) for i in range(random.randrange(200,300)) ]
        #  print(f"before:{check_sort(data)} {data}")
        import time
        start_time=time.time()
        func().sort(data)
        exec_time=time.time()-start_time
        #  print(f"after: {data}")
        print(f"exec_time:{exec_time}")
        assert check_sort(data)
    return test

@wrap_test
def test_selection():
    sort=Selection()
    return sort

@wrap_test
def test_insertion():
    sort=Insertion()
    return sort

@wrap_test
def test_shell():
    sort=Shell()
    return sort

@wrap_test
def test_merge():
    sort=Merge()
    return sort

@wrap_test
def test_quick():
    sort=Quick()
    return sort

if __name__ =="__main__":
    test_quick()
    test_merge()
    test_shell()
    test_insertion()
    test_selection()
